/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2021-10-13
 * Time: 6:35
 */
 class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
 }

public class BinaryTree {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return null;
        }
        if(root==p || root==q){
            return root;
        }
        //递归左树和右树
        TreeNode leftTree=lowestCommonAncestor(root.left,p,q);
        TreeNode rightTree=lowestCommonAncestor(root.right,p,q);
        //当左树和右树都不为空时，最近公共祖先就是根节点
        if(leftTree!=null && rightTree!=null){
            return root;

        }
        //当左树不为空，右树为空时，最近公共祖先就在左树
        if(leftTree!=null && rightTree==null){
            return leftTree;
        }
        //当右树不为空，左树为空时，最近公共祖先就在右树
        if(leftTree==null && rightTree!=null){
            return rightTree;
        }
        return null;
    }
}

